class Solution
{
public:
    // 只允许插入操作
    // dp[i][j]表示前i个数和前j个数的最长公共子串
    enum
    {
        N = 510
    };
    int f[N][N];
    int minInsertions(string s)
    {
        string ss = s;
        reverse(ss.begin(), ss.end());
        for (int i = 1; i <= s.size(); ++i)
            for (int j = 1; j <= ss.size(); ++j)
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (s[i - 1] == ss[j - 1])
                {
                    // if(i == 5 && j == 5) cout << f[i - 1][j - 1] << endl;
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        // cout << f[5][5] << endl;
        return s.size() - f[s.size()][ss.size()];
    }
};